#ifndef BINARYSEARCHTREE_TREE
#define BINARYSEARCHTREE_TREE

#include <iostream>
using namespace std;
//声明二叉搜索树模板类，作用是声明BinaryNode指针
template <typename Comparable>
class BinarySearchTree;

template <typename Comparable>
class BinarySearchTree{
public:
//声明二叉树
    BinarySearchTree(){};
    BinarySearchTree(const BinarySearchTree<Comparable> &rhs){};
//析构函数（用到makeEmpty函数）
    ~BinarySearchTree(){
        makeEmpty();
    };
//找到二叉搜索树中的最小值和最大值
    const Comparable &findMin() const{
        findMin(root);
    };
    const Comparable &findMax() const{
        findMax(root);
    };
//判断元素是否在二叉搜索树中
    bool contains(const Comparable &x) const{
        return contains(x,root);
    };
//判断是否为空树
    bool isEmpty() const{
        if(root != NULL)    return false;
        else    return true;
    };
//中序打印树中的元素
    void printTree() const{
        printTree(root);
    };
//清空树
    void makeEmpty(){
        makeEmpty(root);
    };
//向树中插入元素
    void insert(const Comparable &x){
        insert(x,root);
    };
//移除树中的元素
    void remove(const Comparable &x){
        remove(x,root);
    };
//重载树中的“=”
    const BinarySearchTree<Comparable> &operator=(const BinarySearchTree<Comparable> &rhs){
        root = clone(rhs.root);
        return *this;
    };
private:
//树中成员的声明
    struct BinaryNode{
        Comparable element;
        BinaryNode *left;
        BinaryNode *right;
        BinaryNode( const Comparable &theElement, BinaryNode *lt, BinaryNode *rt)
        : element(theElement), left(lt), right(rt){}
    };
//根为空
    BinaryNode *root=NULL;
//向树中插入元素
    void insert(const Comparable &x, BinaryNode* &t) const{
        if(t == NULL)
        t = new BinaryNode(x, NULL, NULL);
        else if(x < t->element) insert(x, t->left);
        else if(x > t->element) insert(x, t->right);
    }
//移除树中元素
    void remove(const Comparable &x, BinaryNode* &t) const{
        if(t == NULL)   return;
        if(x < t->element)
        remove(x, t->left);
        else if(x > t->element)
        remove(x, t->right);
        else if(t->left !=NULL && t->right != NULL){
        t->element = findMin(t->right)->element;
        remove(t->element, t->right);
        }
        else{
        BinaryNode *oldNode = t;
        t = (t->left != NULL)?t->left:t->right;
        
        delete oldNode;
        }
    }
//找树中的最小值和最大值
    BinaryNode *findMin (BinaryNode *t) const{
        if(t != NULL)
        while(t->left != NULL)
        t = t->left;
        return t;
    }
    BinaryNode *findMax (BinaryNode *t) const{
        if(t != NULL)
        while(t->right != NULL)
        t = t->right;
        return t;
    }
//判断成员函数
    bool contains(const Comparable &x, BinaryNode *t) const{
        if(t == NULL)   return false;
        else if(x < t->element)
        return contains(x, t->left);
        else if(x > t->element)
        return contains(x, t->right);
        else    return true;
    }
//清空函数
    void makeEmpty(BinaryNode* &t){
        if(t != NULL){
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        t = NULL;
    }
//打印树
    void printTree(BinaryNode *t) const{
        if(t->left == NULL&&t->right != NULL){
        cout << t->element << " ";
        printTree(t->right);
        }else if(t->right == NULL && t->left !=NULL){
        printTree(t->left);
        cout << t->element << " ";
        }else if(t->left == NULL && t->right == NULL)
        cout << t->element << " ";
        else{
        printTree(t->left);
        cout << t->element << " ";
        printTree(t->right);
        }
    }
//复制树
    BinaryNode *clone(BinaryNode *t) const{
        if(t == NULL)   return NULL;
        return new BinaryNode(t->element, clone(t->left), clone(t->right) );
    }
};





#endif